/*
 *  Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
 *  *
 *  This file is part of the Open-source Dependency Toolkit (OSDT),
 *  see http://code.google.com/p/open-source-dependency-toolkit.
 *  
 *  The OSDT is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published
 *  by the Free Software Foundation, either version 3 of the License,
 *  or (at your option) any later version.
 * 
 *  The OSDT is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with the OSDT in the file COPYING and COPYING.LESSER. If not, see
 *  http://www.gnu.org/licenses.
 */

package org.osdtsystem.graphs.views;

import org.osdtsystem.exceptions.IllegalCycleException;
import org.osdtsystem.exceptions.FeatureNotFoundException;
import org.osdtsystem.exceptions.InconsistentGraphException;
import org.osdtsystem.exceptions.InconsistentViewException;
import org.osdtsystem.exceptions.LayerNotFoundException;
import org.osdtsystem.exceptions.LocationNotFoundException;
import org.osdtsystem.exceptions.NodeNotFoundException;
import org.osdtsystem.graphs.Graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.osdtsystem.exceptions.IllegalOrderException;
import org.osdtsystem.exceptions.NonUniqueNameException;
import org.osdtsystem.exceptions.OsdtSyntaxException;
import org.osdtsystem.graphs.io.GraphIDs;
import org.osdtsystem.values.EdgeID;
import org.osdtsystem.values.Feature;
import org.osdtsystem.values.Layer;
import org.osdtsystem.values.Location;
import org.osdtsystem.values.NodeID;

/**
 * An unordered, directed tree with edge relation labels. 
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public class TreeEngine implements Tree {
    private Graph graph;
    private final NodeCollection nodeCollection;
    private final Layer treeLayer;
    private final NodeID top;
    
    /**
     * Add an unordered directed tree with edge relation labels to the given 
     * graph. <code>nodeCollection</code> is used as the underlying node collection,
     * and the node <code>top</code> is used as the formal top node of the tree. 
     * The string <code>name</code> is used as the name of the layer used to store edges 
     * in the tree. The tree computes the height for every node in the tree, ie, 
     * the length of the longest path from the node to one of its terminals. The
     * height is used to compute joins, dominance, etc. in an efficient manner. 
     * @param graph the graph used to store the tree
     * @param nodeCollection the collection of nodes in the tree
     * @param top the node used as the top node
     * @param name the name used for the new tree layer
     * @throws NonUniqueNameException 
     */
    public TreeEngine(final Graph graph, final NodeCollection nodeCollection, 
            final NodeID top, final String name) throws NonUniqueNameException {
        this(graph, nodeCollection, top, graph.addLayer(name + ViewConstants.TreeSuffix));

        // Add layer feature for edge relations
        addEdgeFeature(ViewConstants.EdgeRelationFeature);
        addEdgeFeature(ViewConstants.NodeHeightFeature);
        
        // Add view
        graph.addView(this, name);
    }

    /**
     * Create a new view of an existing tree, without adding anything to the graph. 
     * @param graph the graph used to store the tree
     * @param nodeCollection the collection of nodes in the tree
     * @param top the node used as the top node
     * @param treeLayer the layer used to store the edges in the tree
     */
    public TreeEngine(Graph graph, final NodeCollection nodeCollection, 
            final NodeID top, final Layer treeLayer) {
        this.graph = graph;
        this.nodeCollection = nodeCollection;
        this.treeLayer = treeLayer;
        this.top = top;
    }
    
    @Override
    public void addEdgeFeature(final Feature feature) {
        try {
            graph.addLayerFeature(this.treeLayer, feature);
        } catch (LayerNotFoundException ex) {
            throw new InconsistentViewException(
                    "Inconsistent UnorderedTreeEngine: tree layer not found", ex);
        }
    } 

    @Override
    public void addNodeFeature(Feature feature) {
        nodeCollection.addNodeFeature(feature);
    }

    @Override
    public void setFeatureValue(Location location, Feature feature, Object value) 
            throws LocationNotFoundException, FeatureNotFoundException {
        graph.setFeatureValue(location, feature, value);
    }

    @Override
    public EdgeID setParent(NodeID child, NodeID parent, Object relation) 
            throws NodeNotFoundException, IllegalCycleException, IllegalOrderException {
        try {
            // Find old parent edge
            EdgeID oldParentEdge = parentEdge(child);
            
            // Check that child doesn't dominate parent
            if (oldParentEdge != null && (child == parent || dominates(child, parent)))
                throw new IllegalCycleException(
                        "A child node cannot dominate or equal its parent in a tree");
            
            // Delete old parent edge
            NodeID oldParent = null;
            if (oldParentEdge != null) {
                oldParent = parent(oldParentEdge);
                graph.removeEdge(oldParentEdge);
            }
            
            // Create new edge
            EdgeID parentEdge = graph.addEdge(child, parent, treeLayer);
            setRelation(parentEdge, relation);
            
            // Update edge heights
            if (oldParent == null)
                updateHeights(child);
            updateHeights(parent);
            if (oldParent != null)
                updateHeights(oldParent);
            
            // Return edge
            return parentEdge;
        } catch (NodeNotFoundException ex) {
            throw ex;
        } catch(LocationNotFoundException ex) {
            throw new InconsistentGraphException(
                    "Unexpected LocationNotFoundException in setParent", ex);
        }
    }

    @Override
    public NodeID addNode(NodeID parent, Object relation) 
            throws NodeNotFoundException {
        try {
            NodeID child = nodeCollection.addNode();
            setParent(child, parent, relation);
            return child;
        } catch (IllegalCycleException ex) {
            // This should never happen
            throw new InconsistentViewException(
                    "Unexpected cycle in addNode", ex);
        } catch (IllegalOrderException ex) {
            // This should never happen
            throw new InconsistentViewException(
                    "Unexpected illegal order exception in addNode", ex);
        }
    }

    @Override
    public void removeSubtree(final NodeID root) {
        // Never delete the top root!
        if (root == top)
            return;
        
        // Create a list of subroots whose subtrees in the dependency layer must 
        // be deleted
        LinkedList<NodeID> subroots = new LinkedList<NodeID>();
        subroots.add(root);
        
        // Traverse and expand the subroots list in a depth-first manner, 
        // starting from the tail and deleting nodes and edges along the way
        // in order to survive unexpected (illegal) cycles.
        while (! subroots.isEmpty()) {
            // Get newest subroot (to ensure depth-first traversal)
            NodeID subroot = subroots.removeLast();
            
            // Add all dependents of the node to the linked list
            for (EdgeID dependency : graph.outEdges(subroot, treeLayer)) {
                subroots.add(graph.inNode(dependency));
            }
            
            // Delete the node and all its associated edges (including non-dependency
            // edges in other layers) from the graph
            graph.removeNode(subroot);
        }
    }

    @Override
    public NodeID top() {
        return this.top;
    }

    @Override
    public List<EdgeID> edges() {
        return graph.edges(treeLayer);
    }

    @Override
    public List<NodeID> nodes() {
        return nodeCollection.nodes();
    }

    @Override
    public EdgeID parentEdge(NodeID node) {
        List<EdgeID> parents = graph.inEdges(node, treeLayer);
        if (parents.size() == 1)
            return parents.get(0);
        if (parents.size() > 1)
            throw new InconsistentViewException("Invalid tree: non-top node with no parents or multiple parents");
        return null;
    }

    @Override
    public List<EdgeID> childEdges(NodeID node) {
        return graph.outEdges(node, treeLayer);
    }

    @Override
    public boolean dominates(final NodeID dominator, NodeID dominated) {
        try {
            // Find node heights
            int heightDominator = height(dominator);
            int heightDominated = height(dominated);

            // The dominator must be higher than the dominated node
            if (heightDominator <= heightDominated) {
                return false;
            }
            // The dominated node is lower than the dominator; so if we go upwards
            // from the dominated node until we reach the height of the dominator,
            // then we must actually reach the dominator (since this is a tree).
            // Otherwise, the dominates relation doesn't hold.
            while (heightDominator > heightDominated) {
                dominated = parent(parentEdge(dominated));
                if (dominated == null) {
                    return false;
                }
                heightDominated = height(dominated);
            }
            return dominated == dominator;
        } catch (NodeNotFoundException ex) {
            return false;
        }
    }

    
    @Override
    public NodeID join(NodeID node1, NodeID node2) throws NodeNotFoundException {
        // Introduce two hares starting their race at node1 and node2.
        // Let the lowest of the two hares move up the tree, until the two hares
        // reach the same point.
        NodeID hare1 = node1;
        NodeID hare2 = node2;
        int height1 = height(hare1);
        int height2 = height(hare2);
        while (hare1 != hare2) {
            if (height1 <= height2) {
                // Move hare1 one up
                hare1 = parent(parentEdge(hare1));
                height1 = height(hare1);
            } else {
                // Move hare2 one up
                hare2 = parent(parentEdge(hare2));
                height2 = height(hare2);
            }
        }

        // The two hares ended up at the same node (the join)
        return hare1;
    }
    
    @Override
    public List<List<EdgeID>> joinPaths(NodeID node1, NodeID node2) throws NodeNotFoundException {
        // Introduce two hares starting their race at node1 and node2.
        // Let the lowest of the two hares move up the tree, until the two hares
        // reach the same point.
        NodeID hare1 = node1;
        NodeID hare2 = node2;
        int height1 = height(hare1);
        int height2 = height(hare2);
        List<EdgeID> path1 = new ArrayList<EdgeID>();
        List<EdgeID> path2 = new ArrayList<EdgeID>();
        EdgeID parentEdge;
        while (hare1 != hare2) {
            if (height1 <= height2) {
                // Move hare1 one up
                parentEdge = parentEdge(hare1);
                path1.add(parentEdge);
                hare1 = parent(parentEdge);
                height1 = height(hare1);
            } else {
                // Move hare2 one up
                parentEdge = parentEdge(hare2);
                path2.add(parentEdge);
                hare2 = parent(parentEdge);
                height2 = height(hare2);
            }
        }

        // The two hares ended up at the same node (the join)
        List[] paths = {
            Arrays.asList(path1.toArray(new EdgeID[0])),
            Arrays.asList(path2.toArray(new EdgeID[0]))  };
        return Arrays.asList((List<EdgeID>[]) paths);
    }

    @Override
    public int height(NodeID node) throws NodeNotFoundException {
        // Find unchecked feature value storing height
        Object uncheckedHeight;
        if (node == top) {
            // Height for the top node is defined at the treeLayer
            uncheckedHeight = featureValue(treeLayer, ViewConstants.NodeHeightFeature);
        } else {
            // Height for all other nodes are stored at the node's parent edge
            EdgeID parentEdge = parentEdge(node);
            if (parentEdge == null)
                throw new NodeNotFoundException("Cannot find parent edge for node " + node + " in tree");
            uncheckedHeight = featureValue(parentEdge, ViewConstants.NodeHeightFeature);
        }
        
        // Convert unchecked feature value to integer
        if (uncheckedHeight == null)
            return -1;
        else try {
            return ((Integer)uncheckedHeight);
        } catch (ClassCastException ex) {
            throw new InconsistentViewException(
                    "Unexpected non-integer value of height feature for node " + node + " in tree");
        }
    }

    private void setHeight(NodeID node, int height) throws NodeNotFoundException {
        try {
            if (node == top)
                setFeatureValue(treeLayer, ViewConstants.NodeHeightFeature, new Integer(height));
            else {
                EdgeID parentEdge = parentEdge(node);
                if (parentEdge != null)
                    setFeatureValue(parentEdge, ViewConstants.NodeHeightFeature, new Integer(height));
                else
                    throw new NodeNotFoundException("Non-existent node " + node + " in tree");
            }
        } catch (NodeNotFoundException ex) {
            throw ex;
        } catch (LocationNotFoundException ex) {
            throw new NodeNotFoundException("Non-existent node " + node + " in tree");
        } catch (FeatureNotFoundException ex) {
            throw new InconsistentViewException("Inconsistent tree state: no height feature");
        }
    }

    private void updateHeights(NodeID node) throws NodeNotFoundException {
        // Find old height
        int oldHeight = height(node);

        // Find new height
        int newHeight = 0;
        for (EdgeID childEdge : childEdges(node)) {
            int childHeight = height(child(childEdge));
            if (childHeight >= newHeight)
                newHeight = childHeight + 1;
        }
        if (oldHeight != newHeight) {
            setHeight(node, newHeight);
            EdgeID parentEdge = parentEdge(node);
            if (parentEdge != null)
                updateHeights(parent(parentEdge));
        }
    }

    private int initializeHeights(NodeID node) {
        // Find new height
        int newHeight = 0;
        for (EdgeID childEdge : childEdges(node)) {
            int childHeight = initializeHeights(child(childEdge));
            if (childHeight >= newHeight)
                newHeight = childHeight + 1;
        }
        try {
            setHeight(node, newHeight);
        } catch (NodeNotFoundException ex) {
            throw new InconsistentViewException("Cannot initialize height for node " + node, ex);
        }
        return newHeight;
    }
    
    
    @Override
    public NodeID parent(EdgeID dependency) {
        return graph.outNode(dependency);
    }

    @Override
    public NodeID child(EdgeID dependency) {
        return graph.inNode(dependency);
    }

    @Override
    public Object relation(EdgeID edge) {
        return graph.featureValue(edge, ViewConstants.EdgeRelationFeature);
    }
    
    public void setRelation(EdgeID edge, Object relation) 
            throws LocationNotFoundException {
        try {
            graph.setFeatureValue(edge, ViewConstants.EdgeRelationFeature, relation);
        } catch (FeatureNotFoundException ex) {
            throw new LocationNotFoundException("Edge layer does not define " +
                    "EdgeRelationFeature", ex);
        }

    }

    @Override
    public List<Feature> nodeFeatures() {
        return nodeCollection.nodeFeatures();
    }

    @Override
    public List<Feature> edgeFeatures() {
        return graph.features(treeLayer);
    }

    @Override
    public Object featureValue(Location location, Feature feature) {
        return graph.featureValue(location, feature);
    }
    
    @Override
    public void setGraph(final Graph graph) {
        // Check that dependencyLayer and top node exist in graph
        if (! (graph.containsLayer(treeLayer) && graph.containsNode(top)))
            throw new InconsistentViewException("Cannot set new graph in UnorderedTreeEngine:" +
                    " top node or tree layer are not contained in graph");
        
        // Ask node collection to change graph (possibly throwing exception)
        nodeCollection.setGraph(graph);
        
        // Set the graph if everything was ok
        this.graph = graph;
    }

    @Override
    public TreeEngine copy() {
        NodeCollection nodeCollectionCopy = (NodeCollection) nodeCollection.copy();
        return new TreeEngine(this.graph, 
                nodeCollectionCopy, this.top, this.treeLayer);
    }

    @Override
    public void clear() {
        graph.clear(treeLayer);
    }
    
    Graph graph() {
        return graph;
    }
    
    @Override
    public Layer treeLayer() {
        return treeLayer;
    }
    
    NodeCollection nodeCollection() {
        return nodeCollection;
    }
   
    @Override
    public boolean containsNode(NodeID node) {
        return nodeCollection.containsNode(node);
    }
    
    // 1=view ID, 3=node collection, 5=top node, 7=tree layer
    private static final Pattern osdtTreeEnginePattern = Pattern.compile(
            "^\\s*VIEW([0-9]+)\\s+TreeEngine\\((VIEW)?([0-9]+),(NODE)?([0-9]+)," 
            + "(LAYER)?([0-9]+)\\)\\s*$");
    

    @Override
    public String toOSDT(Graph graph, GraphIDs ids) {
        return "TreeEngine(VIEW" + ids.id(nodeCollection) + ","
                + "NODE" + ids.id(top) + ","
                + "LAYER" + ids.id(treeLayer) + ")";
    }

    public static TreeEngine fromOSDT(Graph graph, GraphIDs ids, String osdt)
            throws OsdtSyntaxException {
        // Parse OSDT string
        Matcher m = osdtTreeEnginePattern.matcher(osdt);
        if (! m.find())
            return null;
        
        // Find source and target node collections, and alignment layer
        try {
            // Find view ID, node collection, top node, and tree layer
            int viewID = Integer.parseInt(m.group(1));
            NodeCollection nodeCollection 
                    = (NodeCollection) ids.getView(Integer.parseInt(m.group(3)));
            NodeID top = ids.getNode(Integer.parseInt(m.group(5)));
            Layer treeLayer = ids.getLayer(Integer.parseInt(m.group(7)));
            
            // Create new tree engine
            return new TreeEngine(graph, nodeCollection, top, treeLayer);
        } catch (Exception ex) {
            throw new OsdtSyntaxException("Cannot find view or layer in OSDT string: " + osdt);
        }
    }

    @Override
    public void recompute() {
        initializeHeights(top);
    }


}
